package 优先级队列堆;

import javafx.util.Pair;

import javax.jnlp.IntegrationService;
import java.util.*;

/**
 * 2024年9月8日14:50:58
 * https://leetcode.cn/problems/top-k-frequent-words/description/
 * 前k个高频单词
 */
public class likou692 {

    public static void main(String[] args) {
        Integer a = 1;
        Integer b = 2;

        System.out.println(a.compareTo(b));
        String s = "abc";
        String tmp = new StringBuffer(s).reverse().toString();
        System.out.println( tmp);

        List<Object> list = new ArrayList<>();

    }

    // 练习. 小跟堆中里面存的是 一个数据对. pair
    public List<String> topKFrequent(String[] words, int k) {
        // 1. 统计每个单词出现的次数
        Map<String, Integer> hashMap = new HashMap<>();
        for (String s : words) {
            hashMap.put(s, hashMap.getOrDefault(s, 0) + 1);
        }
        // 2.创建小跟堆. 里面存的是map.  value 是次数
        PriorityQueue<Pair<String, Integer>> heap = new PriorityQueue<>((a, b) -> {
            if (a.getValue() == b.getValue()) {
                // value 是次数, 次数相同, 按照字典序. 从小到大. 求字典序最小的. 相当于是大跟堆
                // todo 比较字典序用的是 compareTo.
                return b.getKey().compareTo(a.getKey());
            }
            // 次数.返回次数多的, 也就是小根堆
            // 两种写法都可以. 整数必须得是包装类, 也可以用 compareTo(). getValue() 返回的是 Integer
            // return a.getValue() - b.getValue();
            return a.getValue().compareTo(b.getValue());
        });
        // 3. TopK的主逻辑
        // 遍历添加元素, 如果超过 size, 弹出栈顶元素, 不可以遍历原字符串, 因为没有去重
        // 一定要学会遍历 map
        // for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
        for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
            heap.offer(new Pair<>(entry.getKey(), entry.getValue()));
            if (heap.size() > k) {
                heap.poll(); // 弹出栈顶元素
            }
        }
        // 4. 收集结果
        List<String> ret = new ArrayList<>();
        while (!heap.isEmpty()) {
            String tmp = heap.poll().getKey(); // 注意还要 getKey(). 就是 String
            ret.add(tmp);
        }
        // 逆置
        Collections.reverse(ret);
        return ret;
    }


    // 练习. 小跟堆中里面存的是 map
    public List<String> topKFrequent2(String[] words, int k) {
        // 1. 统计每个单词出现的次数
        Map<String, Integer> hashMap = new HashMap<>();
        for(String s : words) {
            hashMap.put(s, hashMap.getOrDefault(s, 0) + 1);
        }
        // 2.创建小跟堆. 里面存的是map
        PriorityQueue<Map.Entry<String, Integer>> heap = new PriorityQueue<>((a, b) -> {
            if(a.getValue() == b.getValue()) {
                // value 是次数, 次数相同, 按照字典序. 从小到大. 求字典序最小的. 相当于是大跟堆
                return b.getKey().compareTo(a.getKey());
            }
            // 次数. 小根堆
            // 两种写法都可以
            // return a.getValue() - b.getValue();
            return a.getValue().compareTo(b.getValue());
        });
        // 3. TopK的主逻辑
        // 遍历添加元素, 如果超过 size, 弹出栈顶元素
        // 一定要学会遍历 map
        for(Map.Entry<String, Integer> entry : hashMap.entrySet()) {
            heap.offer(entry);
            if(heap.size() > k) {
                heap.poll(); // 弹出栈顶元素
            }
        }
        // 4. 收集结果
        List<String> ret = new ArrayList<>();
        while(!heap.isEmpty()) {
            String tmp = heap.poll().getKey(); // 注意还要 getKey()
            ret.add(tmp);
        }
        // 逆置
        Collections.reverse(ret);
        return ret;

    }

}
